# class Solution:
#     def findPaths(self, m, n, N, i, j):
#         """
#         :type m: int
#         :type n: int
#         :type N: int
#         :type i: int
#         :type j: int
#         :rtype: int
#         """
#         tmp=[[[0 for i in range(n)] for j in range(m)] for k in range(N+1)]
#         for k in range(1,N+1):
#             for p in range(m):
#                 for q in range(n):
#                     if 0==p:
#                         up=1
#                     else:
#                         up=tmp[k-1][p-1][q]
#                     if m-1==p:
#                         down=1
#                     else:
#                         down=tmp[k-1][p+1][q]
#                     if 0==q:
#                         left=1
#                     else:
#                         left=tmp[k-1][p][q-1]
#                     if n-1==q:
#                         right=1
#                     else:
#                         right=tmp[k-1][p][q+1]
#                     tmp[k][p][q]=(up+down+left+right)%1000000007
#         return tmp[N][i][j]


# solition = Solution()
# print(solition.findPaths(3,3,1,1,1))

# import collections
# def how_likely_alive(m,n,N,i,j):
#     mod = 10**9 + 7
#     Q = collections.deque([(i,j,0)])
#     res = 0
#     while Q:
#         x,y,step = Q.popleft()
#         if step > N: break
#         if 0<=x<m and 0<=y<n:
#             Q.append((x+1,y,step+1))
#             Q.append((x-1,y,step+1))
#             Q.append((x,y+1,step+1))
#             Q.append((x,y-1,step+1))
#         else:
#             res += 1
#     num = res % mod
#     if num == 0:
#         return 1
#     else:
#         return num / 4


def how_likely_alive(m, n, N, i, j):

    tmp=[[[0 for i in range(n)] for j in range(m)] for k in range(N+1)]
    for k in range(1,N+1):
        for p in range(m):
            for q in range(n):
                if 0==p:
                    up=1
                else:
                    up=tmp[k-1][p-1][q]
                if m-1==p:
                    down=1
                else:
                    down=tmp[k-1][p+1][q]
                if 0==q:
                    left=1
                else:
                    left=tmp[k-1][p][q-1]
                if n-1==q:
                    right=1
                else:
                    right=tmp[k-1][p][q+1]
                tmp[k][p][q]=(up+down+left+right)%1000000007

    num = tmp[N][i][j]
    if num == 0:
        return 1
    else:
        return num / 4
    return num


print(how_likely_alive(2,2,1,0,0))